%0 Conference Proceedings
%4 sid.inpe.br/iris@1912/2005/07.19.21.21.48
%2 sid.inpe.br/iris@1912/2005/07.19.21.21.58
%F 8661
%T Uma aplicação da busca TABU ao problema de rotulação cartográfica de pontos
%D 1999
%A Yamamoto, Missae,
%A Camara Neto, Gilberto,
%A Lorena, Luiz Antonio Nogueira,
%B Congresso e Feira para Usuários de Geoprocessamento da América Latina, 5 (GISBRASIL'99).
%C Salvador
%8 1999
%K GEOPROCESSAMENTO, algoritmo de otimização, rotulação cartográfica, busca tabu, rotulação de pontos, cartas, produção cartográfica automatizada.
%X A geracao de configuracoes otimas de rotulos em um mapa e um problema que surge com a producao cartografica autorriatizada. 0 objetivo de uma boa rotulacao e mostrar a posicao geografica das entidades co texto associado, de forma legivel, e respeitando as convencoes cartograficas, com qualidades estetica e harmonica na apresentacao dessas informacoes. Abordamos o problema de rotulacao cartografica sob o ponto de vista de otimizacao combinatoria. Nesta perspectiva, a rotulacao cartografica pertence a classe de problemas de dificil solucao, conduzindo-nos a necessidade de algoritmos de aproximacao, uma vez que nao existe nenhum algoritmo exato capaz de soluciona-lo em um intervalo de tempo aceitavel. Nossa pesquisa consistiu na avaliacao do algoritmo de otimizacao Busca Tabu aplicado a rotulacao cartografica. A Busca Tab implementada no SCARTA, um software de producao cartografico em desenvolvimento pela Divisão de Processamento de Imagens (DPI/INPE), mostrou-se um algoritmo eficiente, nos casos-teste real e aleatorio. Quando comparado a tecnicas alternativas como "Simulated Annealing", algoritmo genetico com mascara, e outras descritas na literatura, a Busca Tabu apresentou o melhor desempenho em qualidade. Concluimos que a Busca Tabu e um metodo recomendavel para solucao de problema de rotulacao cartografica de pontos, devido a sua simplicidade, praticidade, eficiencia e bom desempenho, conjugado a capacidade de gerar solucoes de qualidade em tempo computacional aceitavel. ABSTRACT: The generation of better label placement configurations in maps is a problem that comes up in automated cartographic production. The objective of a good label placement is to show the geographic position of the features with their corresponding texts clearly, respecting the cartographic conventions, with an esthetic and a harmonious quality when present , ing the information. We approached the label placement problem from a combinatorial optimization point of view. In this perspective, the cartographic label placement belongs to a problem area of difficult solution, leading us to the need of approximation algorithms as there is no exact algorithm that is able to solve this problem within an acceptable amount of time. Our research consisted in the evaluation of the tabu search optimization algorithm applied to cartographic label placement. The tabu search implemented in SCARTA, a cartographic production software, in development by the Image Processing Division (DPI/INPE), proved to be an efficient algorithm, in real and random test cases. When compared with alternative techniques such as "simulated annealing", genetic algorithm with mask and others described in literature, the tabu search had the best performance in quality. We concluded that tabu search is a recommended method to solve cartographic label placement problem of point features, due to its simplicity, practicality, efficiency and good performance along with its ability to generate quality solutions in acceptable computational time.
%@language pt
%3 1998_yamamoto.pdf